package blue_bridge_cup_learning.整数划分;

public class 整数划分模板 {
    public static void main(String[] args) {
        int[] arr = { 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 8 };
        System.out.println("得到arr中等于x最左边的元素的下标：" + getL(arr, 0, arr.length - 1, 3));
        System.out.println("得到arr中等于x最右边的元素的下标：" + getR(arr, 0, arr.length - 1, 4));
        System.out.println("得到arr中大于等于x的元素的下标：" + lower_index(arr, 0, arr.length - 1, 4));
        System.out.println("得到arr中小于第一个大于x的元素的下标：" + upper_index(arr, 0, arr.length - 1, 4));
    }

    public static int getL(int arr[], int l, int r, int x) {
        while (l < r) {
            int mid = l + r >> 1;
            if (x <= arr[mid]) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        if (arr[l] != x) {
            return -1;
        }
        return l;
    }

    public static int getR(int arr[], int l, int r, int x) {
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (x >= arr[mid]) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return l;
    }

    public static int lower_index(int[] arr, int l, int r, int x) {
        if (x > arr[r]) {
            return -1;
        }
        while (l < r) {
            int mid = l + r >> 1;
            if (x <= arr[mid]) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }

    public static int upper_index(int[] arr, int l, int r, int x) {
        if (x >= arr[r]) {
            return -1;
        }
        while (l < r) {
            int mid = l + r >> 1;
            if (x < arr[mid]) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}
